1. Field of the Invention
The present invention generally relates to activity/event monitoring in various application areas such as business activity monitoring for corporate management, sensor activities monitoring for continual queries, road traffic condition monitoring for traffic control, event matching for pub/sub applications, information monitoring for selective information dissemination, and health activity monitoring for disease outbreaks or bio-attacks. More specifically, it discloses a predicate/query indexing method for monitoring activities/events against a plurality of continual range predicates/queries.
2. Description of the Related Art
Fast matching of events against a large number of predicates/queries is important for many applications, such as business activity monitoring, content-based pub/sub (publication/subscription), continual queries, health activity monitoring, and selective information dissemination services. Users simply specify their interests in the form of a conjunction of predicates. The system then automatically monitors these user interests against a continual stream of events, conditions, or activities.
Generally, an efficient predicate index is needed. Prior work for fast event monitoring has mostly focused on building predicate indexes with equality-only clauses, as in, for example:                “Matching events in a content-based subscription system,” by M. K. Aguilera et al., in Proc. of Symposium on Principles of Distributed Computing, 1999; and        “Filtering algorithms and implementation for very fast publish/subscribe systems,” by F. Fabret et al., in Proc. of ACM SIGMOD, 2001.        
However, many queries/predicates contain non-equality range clauses. For example, stock price, salary, and object location tend to involve non-equality range predicates.
It is difficult to construct an effective index for multidimensional range predicates. It is even more challenging if these predicates are overlapping, as they usually are because people tend to share similar interests. For instance, people tend to be interested in the current price ranges of individual stocks. Hence, the range predicates of their interests are likely to be overlapping.
Although multidimensional range predicates can be treated as spatial objects, a typical spatial index, such as an R-tree, is generally not effective for monitoring events. This is because an R-tree method is generally a disk-based indexing method and an R-tree quickly degenerates if spatial objects are highly overlapping (V. Gaede et al., “Multidimensional access methods,” ACM Computing Surveys, 30(2):170-231, 1998.; A. Guttman, “R-trees: A dynamic index structure for spatial searching,” Proceedings of ACM SIGMOD, 1984.)
Hence, a need is recognized for a new and effective system and method for efficient monitoring of events against range queries, some of them may overlap with one another.